Search for: All records

Let $$m_G$$ denote the number of perfect matchings of the graph $$G$$. We introduce a number of combinatorial tools for determining the parity of $$m_G$$ and giving a lower bound on the power of 2 dividing $$m_G$$. In particular, we introduce certain vertex sets called channels, which correspond to elements in the kernel of the adjacency matrix of $$G$$ modulo $$2$$. A result of Lovász states that the existence of a nontrivial channel is equivalent to $$m_G$$ being even. We give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound on the power of $$2$$ dividing $$m_G$$ when $$G$$ is planar. We describe a number of local graph operations which preserve the number of channels. We also establish a surprising connection between 2-divisibility of $$m_G$$ and dynamical systems by showing an equivalency between channels and billiard paths. We exploit this relationship to show that $$2^{\frac{\gcd(m+1,n+1)-1}{2}}$$ divides the number of domino tilings of the $$m\times n$$ rectangle. We also use billiard paths to give a fast algorithm for counting channels (and hence determining the parity of the number of domino tilings) in simply connected regions of the square grid. 

Abstract The $$(P, \omega )$$-partition generating function of a labeled poset $$(P, \omega )$$ is a quasisymmetric function enumerating certain order-preserving maps from $$P$$ to $${\mathbb{Z}}^+$$. We study the expansion of this generating function in the recently introduced type 1 quasisymmetric power sum basis $$\{\psi _{\alpha }\}$$. Using this expansion, we show that connected, naturally labeled posets have irreducible $$P$$-partition generating functions. We also show that series-parallel posets are uniquely determined by their partition generating functions. We conclude by giving a combinatorial interpretation for the coefficients of the $$\psi _{\alpha }$$-expansion of the $$(P, \omega )$$-partition generating function akin to the Murnaghan–Nakayama rule.